package demo.practice.leetcode_unionfind;

public class P547 {


    private class UnionFindSet {
        private int count = 0;
        private int[] parents;

        public UnionFindSet(int[][] M) {
            int n = M.length;
            parents = new int[n];
            for (int i = 0; i < n; ++i) {
                parents[i] = i;
            }
            count = n;
        }

        public int find(int i) {
            if (i != parents[i]) {
                parents[i] = find(parents[i]);
            }
            return parents[i];
        }

        public void union(int i, int j) {
            int rootI = find(i), rootJ = find(j);
            if (rootI != rootJ) {
                parents[rootI] = rootJ;
                --count;
            }
        }

        public int getCount() {
            return count;
        }
    }

    public int findCircleNum(int[][] M) {
        if (M == null || M.length == 0) {
            return 0;
        }
        int n = M.length;
        UnionFindSet ufs = new UnionFindSet(M);
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (M[i][j] == 1) {
                    ufs.union(i, j);
                }
            }
        }
        return ufs.getCount();
    }
}
